#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-28 9:57 上午
# @Author  : yangdy
# @File    : 2020-09-28.117.填充每个节点的下一个右侧节点指针II
# @Software: PyCharmCE
from tools.my_methods import *


"""
# Definition for a Node.
"""


class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


def _display(root, dep=0, keys=['val']):
    if not root:
        return
    _display(root.right, dep+1)
    keys_arr = []
    for key in keys:
        keys_arr.append((key, getattr(root, key)))
    keys_str = ','.join(map(lambda q: f'{q[0]}:{q[1]}', keys_arr))
    print(' '*dep, keys_str)
    _display(root.left, dep=dep+1, keys=keys)


class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # display(root)
        # 1. 分层广度优先搜索bfs
        # que = [root]
        # while que:
        #     new_que = []
        #     for qi in que:
        #         if qi and qi.left:
        #             new_que.append(qi.left)
        #         if qi and qi.right:
        #             new_que.append(qi.right)
        #     for i in range(1, len(new_que)):
        #         new_que[i-1].next = new_que[i]
        #     que = new_que
        # 2. 分层bfs优化
        cur = root
        dummy = Node(0)
        while cur:
            dummy.next = None
            pre = dummy
            while cur:
                if cur.left:
                    pre.next = cur.left
                    pre = pre.next
                if cur.right:
                    pre.next = cur.right
                    pre = pre.next
                cur = cur.next
            cur = dummy.next

        # _display(root, keys=['val', 'next'])
        return root


questions = [
    ([1, 2, 3, 4, 5, None, 7],)
]


work(questions, lambda q: Solution().connect(mk_tree(q[0], Node)))
